Codeforces Round 525 (Div. 2)

Diposting di | Edited on

传送门

A. Ehab and another construction problem(水题，暴力)

题解

虽然是水题但是我还是要讲一下，这个题目的范围一看就知道暴力一下就可以求出答案，但是我一开始看到这题的时候确实懵逼了一会，感觉这题有很明显的规律，后来看了别人的代码终于发现了，就是除了1之外，其他任意的数x都可以用x表示a和b 完美符合条件，这样复杂度只要O（1） 而且暴力就过不去了。

1
2
3
4
int x;
cin>>x;
if(x==1)cout<<-1<<endl;
else cout<<x<<" "<<x<<endl;

B.Ehab and subtraction (排序，优先队列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
priority_queue<int,vector<int>,greater<int> >pq;
int main()
{
    int n,k;
    cin>>n>>k;
    while(n--){
        int a;
        cin>>a;
        pq.push(a);
    }
    int num=0;
    while(k--){
        if(pq.empty())cout<<0<<endl;
        else{
            int sum=pq.top();pq.pop();
            while(!pq.empty()&&pq.top()==sum)pq.pop();
            if(sum-num<=0)cout<<0<<endl;
            else cout<<sum-num<<endl;
            num=sum;
        }
    }
    return 0;
}

C.Ehab and a 2-operation task (思维)

题意

给定一个长度为 n 的数组a[ ]，并且有两种操作：

　　①将前 i 个数全都加上 x;

　　②将前 i 个数全都 mod x

　　要求用不超过 n+1 次操作，使得数组 a[ ] 严格单调递增。

题解

注意mod可以把一个大的数变成一个我们想要的一个数（前提，这个数必须比我们想要的那个数大很多)

可以把n 个数全部加上一个超级大的值,然后 取模 强行组成为递增的数组即可。

1
2
3
4
5
6
7
8
9
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cout<<n+1<<endl;
cout<<"1 "<<n<<" 100000"<<endl;
for(int i=1;i<=n;i++){
    cout<<2<<" "<<i<<" "<<(100000+a[i]-(i-1))<<endl;
    //cout<<(100000+a[i])%(100000+a[i]-(i-1))<<endl;
}

D.Ehab and another another xor problem (思维,位运算)

题意

系统中有两个数(a,b)，请使用62以内次询问来确定出(a,b)

每次可以询问两个数(c,d)

若a⊕c>b⊕da⊕c>b⊕d返回11

若a⊕c=b⊕da⊕c=b⊕d返回00

若a⊕c<b⊕da⊕c<b⊕d返回−1−1

保证/需要保证0⩽a,b,c,d,<2^30

题解

我是，先判断一下a,b
然后a如果大于b
判断是不是因为多了最高位
然后a和b都亦或最高位
如果a小于说明是最高位起作用了 同时不能确定后面的小位谁大谁小
如果a还是大于 说明是相同的然后把a亦或一个1 (相当于把1去掉)如果小于就说明原本都是1 不然就是0 同时这样可以知道a还是比b大
然后b大于a同理
等于就判断是0还是1
这样每一位都判断两次，应该是30*2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
int a,b;
int top=29;
int who=0;
void run();
void getmax(){
    if(top<0)return;
    cout<<"? "<<a<<" "<<b<<endl;
    fflush(stdout);
    cin>>who;
    run();

}
/*
1000011
1000111
*/
void run(){
    if(top<0)return;
    if(who==1){
        cout<<"? "<<(a|(1<<top))<<" "<<(b|(1<<top))<<endl;
        fflush(stdout);
        cin>>who;
        if(who==-1)a|=(1<<top),top--,getmax();
        else{
            cout<<"? "<<(a|(1<<top))<<" "<<b<<endl;
            fflush(stdout);
            cin>>who;
            if(who==-1)a|=(1<<top),b|=(1<<top),top--,who=1,run();
            else top--,who=1,run();
        }
        return;
    }
    else if(who==-1){
        cout<<"? "<<(a|(1<<top))<<" "<<(b|(1<<top))<<endl;
        fflush(stdout);
        cin>>who;
        if(who==1)b|=(1<<top),top--,getmax();
        else{
            cout<<"? "<<a<<" "<<(b|(1<<top))<<endl;
            fflush(stdout);
            cin>>who;
            if(who==1)a|=(1<<top),b|=(1<<top),top--,who=-1,run();
            else top--,who=-1,run();
        }
        return;
    }
    else{
        cout<<"? "<<(a|(1<<top))<<" "<<b<<endl;
        fflush(stdout);
        cin>>who;
        if(who==-1)a|=(1<<top),b|=(1<<top),top--,getmax();
        else top--,getmax();
    }
}
int main(){
    getmax();
    cout<<"! "<<a<<" "<<b<<endl;
    fflush(stdout);
    return 0;
}

E.Ehab and a component choosing problem (树形DP，贪心)

题意

给出一棵树，每个节点有权值，选出k个联通块，最大化

题解

结论：选出的kk个联通块的大小是一样的且都等于最大联通块的大小(参考博客https://www.cnblogs.com/zwfymqz/p/10069374.html)

证明：因为我们是在保证分数最大的情况下才去最大化k，一个很经典的结论是单独选择一个权值最大的联通块得到的分数一定是最大的，然后我们这时我们才去考虑最大化k

那么思路就很清晰了，先一遍dfs dp出最大联通块，然后再一遍dfs从下往上删就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
vector<int>ve[maxn];
ll value[maxn];
ll dp[maxn];
ll dp2[maxn];
void add(int x,int y){
    ve[x].push_back(y);
    ve[y].push_back(x);
}
ll ans=-inf;
void dfs(int now,int pre){
    dp[now]=value[now]*1LL;
    int sz=ve[now].size();
    for(auto i:ve[now]){
        if(i==pre)continue;
        dfs(i,now);
        dp[now]=max(dp[now],dp[now]+dp[i]);
    }
    ans=max(ans,dp[now]);
}
ll num;
void dfs1(int now,int pre){
    dp2[now]=value[now]*1LL;
    int sz=ve[now].size();
    for(auto i:ve[now]){
        if(i==pre)continue;
        dfs1(i,now);
        dp2[now]=max(dp2[now],dp2[now]+dp2[i]);
    }
    if(dp2[now]==ans)num++,dp2[now]=0;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>value[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    dfs(1,0);dfs1(1,0);
    cout<<1LL*ans*num<<" "<<num<<endl;
    return 0;
}